package com.appspot.theonionorthenews;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import javax.persistence.EntityManager;
import javax.persistence.EntityTransaction;
import javax.persistence.Query;

import com.google.appengine.api.datastore.KeyFactory;
import com.google.appengine.api.memcache.InvalidValueException;
import com.google.appengine.api.memcache.MemcacheService;

/**
 * Storage access for news items, combining datastore and memcache.
 *
 * In general, we cannot trust the cache to be "current" (because it can be
 * flushed at any moment, so even though increment <em>is</em> guaranteed
 * to be atomic, the reseeding of the incremented value is not), but we can
 * trust it to be "consistent" modulo the fact that elements might be flushed.
 *
 * In practice, this means that the datastore is always authoritative, and
 * all writes should go to it and should flush dirty cache entries.  Reloading
 * them is not necessary, and is in fact problematic, because the cache reload
 * would not be atomic and might not be correct if another thread is tweaking
 * the datastore at the same moment.
 *
 * The cache contains keys for news items by id, by draw id, and for the high
 * water mark of max used draw id.  (The datastore keeps track of ids by
 * itself.)
 */
public class CachedNewsStorage {

  /** Exception thrown if we try to operate in a missing or ambigous group. */
  public static class BadGroupException extends Exception {

    private static final long serialVersionUID = 1L;

    public BadGroupException(String message) {
      super(message);
    }
  }

  /**
   * Prefix on memcache storage of max draw id.  That sounds monotonic, but
   * isn't; also, the max draw in cache may not exactly match that in the
   * datastore.  Normally, the cache will be right; it might be one or a few
   * items behind (in race conditions as new items are added), but it might
   * also be one or a few <em>behind</em> as items are moved to fill "gaps"
   * in the draw.  Because of this, the key is flushed as a gap is filled,
   * and code must handle no-such-draw-id for both the "gap" and the "too
   * high" cases.
   */
  static final String MAX_DRAW_KEY = "maxdraw";

  private static final String DEFAULT_GROUP = "theonionorthenews";

  /** Prefix on memcache storage of news items by draw. */
  private static final String DRAW_KEY_PREFIX = "draw-";

  /** Prefix on memcache storage of news items by id. */
  private static final String ID_KEY_PREFIX = "id-";

  /** Minimum number of guesses before we consider retiring an item. */ 
  private static final long MIN_GUESS_THRESHOLD = 100;

  /**
   * Once {@link #MIN_GUESS_THRESHOLD} is reached, if the ratio of correct
   * answers is at least this, we retire the item from drawings as being
   * "boring" since it seems too many people know the answer.
   */
  private static final double MAX_CORRECT_RATIO = 0.75;

  /**
   * Maximum results for a query by draw id.  There are corner cases where it
   * might not be unique, but should only have at most a few duplicates to be
   * corrected.  This constant ensures that "only a few" can't swamp us if that
   * expectation goes haywire. 
   */
  private static final int MAX_QUERY_RESULTS = 10;

  protected Random random;
  private EntityManager em;
  private MemcacheService cache;
  private NewsGroupEntity group;

  private static String drawKey(NewsItemEntity item) {
    return drawKey(item.getDrawId()); 
  }

  private static String idKey(NewsItemEntity item) {
    return idKey(item.getId()); 
  }

  private static String getKind(Class<?> type) {
    String name = type.getName();
    int lastDot = name.lastIndexOf('.');
    return name.substring(lastDot + 1);
  }

  static String drawKey(long draw) {
    return DRAW_KEY_PREFIX + draw;
  }

  static String idKey(long id) {
    return ID_KEY_PREFIX + id;
  }

  /** Ensure a given word is SQL-safe to be a quoted word. */
  private static String sqlWord(String unsafe) {
    return unsafe.replace("'", "");
  }

  public CachedNewsStorage(EntityManager em, MemcacheService cache) throws BadGroupException {
    this(em, cache, DEFAULT_GROUP);
  }

  public CachedNewsStorage(EntityManager em, MemcacheService cache, String name) throws BadGroupException {
    this.em = em;
    this.cache = cache;
    this.group = getGroup(name);
    random = new Random();
  }

  /**
   * Gets a random news item, or {@code null} if none exist.  Possibly needs
   * several draws, and perhaps write operations, since the draw ids can have
   * gaps that are backfilled as discovered.
   */
  public NewsItemEntity getRandomDraw() {
    long max = getMaxDrawId();
    if (max <= 0) {
      return null;  // no possible draw to fetch.
    }

    while (true) {
      long draw = random.nextLong() % max;
      if (draw <= 0) {
        draw += max;
      }
      NewsItemEntity item = getByDrawId(draw);
      if (item != null) {
        return item;
      }
      // that draw id is dead, either backfill it or draw another.
      NewsItemEntity backfill = getByDrawId(max);
      if (backfill != null) {
        List<String> list = new ArrayList<String>(2);
        list.add(MAX_DRAW_KEY);
        list.add(drawKey(backfill));
        backfill.setDrawId(draw);
        em.persist(backfill);
        cache.put(drawKey(backfill), backfill);
        cache.deleteAll(list);
        return backfill;
      }
      // Here, we know that our cache is wrong; the cached max draw doesn't
      // exit.  Either it's too high (and we're over the real max) or it's too
      // low but there's a gap.  Either way, recompute the right max and loop
      // again trying from there.
      max = refreshCachedMaxDraw();
    }
  }

  public void update(NewsItemEntity item) {
    if (item.getGuessCount() > MIN_GUESS_THRESHOLD) {
      double correctRatio = ((double) item.getCorrectGuessCount()) / item.getGuessCount();
      if (correctRatio > MAX_CORRECT_RATIO) {
        // Too many people have guessed too well; this item is boring.
        item.clearDrawId();
      }
    }
    em.merge(item);
    if (item.getId() < 1) {
      // If id is unset, as for a new item, then read it back so we know it:
      em.refresh(item);
    }
    List<String> dirtyKeys = new ArrayList<String>(3);
    if (item.getId() > 0) {
      // For new items, they won't yet have an id (we don't do a round-trip
      // write & read), so they don't have a dirty id key.
      dirtyKeys.add(idKey(item));
    }
    if (item.getDrawId() != null) {
      dirtyKeys.add(drawKey(item));
    }
    dirtyKeys.add(MAX_DRAW_KEY);
    cache.deleteAll(dirtyKeys);
  }

  public NewsItemEntity add(NewsItemEntity item) {
    EntityTransaction txn = em.getTransaction();
    boolean beganHere = !txn.isActive();
    try {
      txn.begin();
      long nextDraw = allocateNewDrawId();
      item.setDrawId(nextDraw);
      item.setGroup(group);
      update(item);
      if (beganHere) {
        txn.commit();
      }
    } finally {
      if (beganHere && txn.isActive()) {
        txn.rollback();
      }
    }
    return item;
  }

  public NewsItemEntity getById(long id) {
    NewsItemEntity cachedItem = (NewsItemEntity) cache.get(idKey(id));
    if (cachedItem != null) {
      return cachedItem;
    }

    NewsItemEntity result = em.find(NewsItemEntity.class, 
        KeyFactory.createKey(// TODO: group.getKey(),
            getKind(NewsItemEntity.class), id));
    if (result == null) {
      return null;
    }
    cache.put(idKey(id), result);
    return result;
  }

  /**
   * Loads a news item by its draw id, or returns {@code null} if there is no
   * such item.  There might be no item because of a gap in draw ids, or a
   * race condition to fill such a gap.  It is also possible for multiple items
   * to have been "accidentally" assigned the same draw id; in that case, this
   * call will pick one to keep the draw id and reassign the others to unused
   * draw ids.
   *
   * @returns The item with the requested draw id, or {@code null} if there are
   *     none.
   */
  public NewsItemEntity getByDrawId(long draw) {
    NewsItemEntity cachedItem = (NewsItemEntity) cache.get(drawKey(draw));
    if (cachedItem != null) {
      return cachedItem;
    }

    Query query = em.createQuery(String.format(  // TODO: add where n.group...
        "select n from NewsItemEntity n where n.drawId = %s", draw));
    query.setMaxResults(MAX_QUERY_RESULTS);  // Allow for up to several duplicates.
    @SuppressWarnings("unchecked")
    List<NewsItemEntity> list = (List<NewsItemEntity>) query.getResultList();
    if (list.isEmpty()) {
      return null;
    }
    cache.put(drawKey(draw), list.get(0));
    if (list.size() > 1) {
      for (int i = 1; i < list.size(); i++) {
        reallocateDuplicateDraw(list.get(i), allocateNewDrawId());
      }
      cache.delete(MAX_DRAW_KEY);
    }
    return list.get(0);
  }

  /** Testing setting to fix random generator. */
  void setRandomForTesting(Random newRandom) {
    this.random = newRandom;
  }

  /**
   * Gets the max draw id currently in use.  There are potential race
   * conditions, of course; the maximum draw ID used may move either up
   * <i>or down</i> immediate after or, in some cases, even during this
   * call.
   *
   * @return The maximum assigned draw identifier.
   */
  long getMaxDrawId() {
    Long cacheMax = (Long) cache.get(MAX_DRAW_KEY);
    if (cacheMax != null) {
      return cacheMax;
    }
    return refreshCachedMaxDraw();
  }

  /**
   * Allocates a new draw id, relying on (and if necessary populating) the
   * cache entry, such that MemCache.increment can be used to allocate.  The
   * algorithm for this is not perfect; it relies on the cache key being set
   * accurately, which in turn relies on a lack of race conditions between
   * loading the cache and writes to the datastore, which is not strictly
   * assured. This risk is mostly hypothetical---the key is accessed often and
   * should not be discarded from the cache---but the algorithms need to be
   * permissive of possible gaps or duplicate assignments.
   * 
   * @return a "fairly confident" next usused draw id.
   */
  private long allocateNewDrawId() {
    try {
      return cache.increment(MAX_DRAW_KEY, 1);
    } catch (NullPointerException e) {
      // okay, not in cache; get it from the datastore.
    } catch (InvalidValueException e) {
      // okay, bad value in cache; recompute it.
    }
    long max = refreshCachedMaxDraw();
    try {
      return cache.increment(MAX_DRAW_KEY, 1);
    } catch (InvalidValueException e) {
      // Um.  How?  But we don't have to give up, just fall through.
    } catch (NullPointerException e) {
      // Cache is off or flushing always, so do a non-atomic approximate.
    }
    return max + 1;
  }

  private NewsGroupEntity getGroup(String name) throws BadGroupException {
    name = sqlWord(name);
    NewsGroupEntity group = em.find(NewsGroupEntity.class,
        KeyFactory.createKey(getKind(NewsGroupEntity.class), name));
    if (group == null) {
      EntityTransaction txn = em.getTransaction();
      txn.begin();
      group = new NewsGroupEntity(name);
      em.persist(group);
      txn.commit();
    }
    return group;
  }

  /**
   * Recomputes the cache entry for {@link #MAX_DRAW_KEY} from the
   * persistent data store.
   *
   * @return The maximum assigned draw identifier; as a side effect, this is
   *    also stored in the cache (replacing any previous value there).
   */
  private long refreshCachedMaxDraw() {
    Query query = em.createQuery(// TODO: ...where n.group = this.group...
        "select n from NewsItemEntity n order by n.drawId desc");
    query.setMaxResults(MAX_QUERY_RESULTS);  // Allow for a limited number of duplicates.

    @SuppressWarnings("unchecked")
    List<NewsItemEntity> list = (List<NewsItemEntity>) query.getResultList();

    long answer = 0;
    boolean cacheAnswer = true;  // Whether we trust our answer and should cache it.
    if (!list.isEmpty()) {
      NewsItemEntity news = list.get(0);
      answer = news.getDrawId();
      long firstAnswer = answer;
      // Walk the list to check for duplicate id's, which we hope not to find.
      for (int i = 1; i < list.size(); ++i) {
        NewsItemEntity laterItem = list.get(i);
        if (laterItem.getDrawId() != firstAnswer) {
          break;  // no more duplicates, good.
        }
        cacheAnswer = false;
        reallocateDuplicateDraw(laterItem, ++answer);
      }
    }
    if (cacheAnswer) {
      cache.put(MAX_DRAW_KEY, answer);
    }
    return answer;
  }

  /** Deals with possible duplicate draw ids. */
  private void reallocateDuplicateDraw(NewsItemEntity newsItem, long newDraw) {
    cache.delete(idKey(newsItem));
    newsItem.setDrawId(newDraw);
    EntityTransaction txn = em.getTransaction();
    try {
      txn.begin();
      update(newsItem);
      txn.commit();
    } finally {
      if (txn.isActive()) {
        txn.rollback();
      }
    }
  }
}
